import numpy as np
import copy
from datetime import datetime

# 定位元素0的位置
def local(S0):
    a = np.array(S0)
    i, j = np.where(a == 0)
    return i[0], j[0]

def move(S0, direction):
    i, j = local(S0)
    arr = copy.deepcopy(S0)
    
    if direction == 'right':
        if j < len(S0) - 1:
            arr[i][j], arr[i][j+1] = arr[i][j+1], arr[i][j]
    elif direction == 'left':
        if j > 0:
            arr[i][j], arr[i][j-1] = arr[i][j-1], arr[i][j]
    elif direction == 'up':
        if i > 0:
            arr[i][j], arr[i-1][j] = arr[i-1][j], arr[i][j]
    elif direction == 'down':
        if i < len(S0) - 1:
            arr[i][j], arr[i+1][j] = arr[i+1][j], arr[i][j]
    
    return arr

class Node:
    def __init__(self, data, level, parent, score):
        self.data = data
        self.level = level
        self.parent = parent
        self.score = score

def Atest_g(S0, Sg):
    S1 = np.reshape(S0, (3, 3))
    Sg = np.reshape(Sg, (3, 3))
    g = 0
    for i in range(len(S1)):
        for j in range(len(S1[i])):
            if S1[i][j] != Sg[i][j] and S1[i][j] != 0:
                g += 1
    return g

def Asort(open_):
    open_.sort(key=lambda x: x.score)
    return open_

if __name__ == "__main__":
    S0 = [[2, 8, 3], [1, 6, 4], [7, 0, 5]]
    Sg = [[1, 2, 3], [8, 0, 4], [7, 6, 5]]

    Node0 = Node(S0, 0, "None", 0)

    deep_level = 5

    open_ = [Node0]
    close = []

    step = 0

    start = datetime.now()
    while len(open_) > 0:
        step += 1
        n = open_.pop(0)
        close.append(n)

        if n.data == Sg:
            print(n.data, 'true', '搜索完毕！')
            result = []
            result.append(n)
            while n.parent != "None":
                result.append(n.parent)
                n = n.parent
            for j in range(len(result)):
                print(str(j) + "->")
                result_0 = result.pop(-1)
                print(result_0.data)
            print("------------结束搜索-----------")
            break
        else:
            for direction in ['up', 'down', 'left', 'right']:
                new_state = move(n.data, direction)
                if new_state is not None and new_state not in [x.data for x in open_] and new_state not in [x.data for x in close]:
                    new_node = Node(new_state, n.level + 1, n, (Atest_g(new_state, Sg) + n.level + 1))
                    open_.append(new_node)
        
        Asort(open_)
        print(f"第{step}次查找,中间项为：{n.data}, 深度为:{n.level}, 估价值为：{n.score}")
    
    end = datetime.now()

    print('共耗时:', end - start)